home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1994 November / macformat-018.iso / Utility Spectacular / Utilities / Calc / alloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-24  |  13.1 KB  |  607 lines  |  [TEXT/????]
  1. /*
  2.  * Copyright (c) 1992 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * Description:
  7.  *    This is a very fast storage allocator. It allocates blocks of a small
  8.  *    number of different sizes, and keeps free lists of each size.  Blocks
  9.  *    that don't exactly fit are passed up to the next larger size.  In this
  10.  *    implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  11.  *    This is designed for use in a program that uses vast quantities of
  12.  *    memory, but bombs when it runs out.
  13.  *
  14.  * Abnormal Conditions
  15.  *    This is a public domain storage allocator.
  16.  *
  17.  * Modifications:
  18.  *    Date        Programmer        Description of modification
  19.  *    27-FEB-90    Landon Curt Noll    unix does not need most of this
  20.  *    2-OCT-89    David I. Bell        Add free list. Sbrk now optional
  21.  *    30-JUN-87    Peter Miller        Made it work on Slimos.
  22.  *    21-FEB-82    Chris Kingsley        Initial Coding
  23.  *            kingsley@cit-20        Caltech
  24.  */
  25.  
  26. #include <stdio.h>
  27. #include "alloc.h"
  28. #include "have_stdlib.h"
  29.  
  30. #if 0
  31. #define DEBUG    1        /* defined if debugging code enabled */
  32. #define MSTATS    1        /* defined if memory statistics kept */
  33. #endif
  34. #define    NO_SBRK    1        /* defined if cannot use sbrk */
  35.  
  36.  
  37. #if !defined(UNIX_MALLOC)
  38. /*
  39.  * Make these functions really accessible here.
  40.  */
  41. #undef    malloc
  42. #undef    realloc
  43. #undef    free
  44.  
  45.  
  46. #ifdef DEBUG
  47. #define assert(x,v) if ((x)==0) assertfailed(v)
  48. #else
  49. #define assert(x,v)
  50. #endif
  51.  
  52. typedef unsigned char u_char;
  53. typedef unsigned short u_short;
  54. typedef unsigned int u_int;
  55. typedef char * caddr_t;
  56.  
  57. #ifdef NO_SBRK
  58. extern char * malloc();
  59. extern char * realloc();
  60. #else
  61. extern char * sbrk();
  62. #endif
  63.  
  64.  
  65. /*
  66.  * The overhead on a block is at least 4 bytes.  When free, this space
  67.  * contains a pointer to the next free block, and the bottom two bits must
  68.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  69.  * byte is the size index.  The remaining bytes are for alignment.
  70.  * If range checking (RCHECK) is enabled and the size of the block fits
  71.  * in two bytes, then the top two bytes hold the size of the requested block
  72.  * plus the range checking words, and the header word MINUS ONE.
  73.  */
  74.  
  75. union overhead
  76. {
  77.     union overhead * ov_next;    /* when free */
  78.     struct
  79.     {
  80.         u_char ovu_magic;    /* magic number */
  81.         u_char ovu_index;    /* bucket # */
  82. #define ov_magic ovu.ovu_magic
  83. #define ov_index ovu.ovu_index
  84. #ifdef RCHECK
  85.         u_short ovu_size;    /* actual block size */
  86.         u_int ovu_rmagic;    /* range magic number */
  87. #define ov_size ovu.ovu_size
  88. #define ov_rmagic ovu.ovu_rmagic
  89. #endif
  90.     } ovu;
  91. };
  92.  
  93. #define QUANTUM_NBITS    4
  94. #define QUANTUM        (1<<QUANTUM_NBITS)
  95.  
  96. #define MAGIC    0xff        /* magic # on accounting info */
  97. #define RMAGIC    0x55555555    /* magic # on range info */
  98. #ifdef RCHECK
  99. #define RSLOP    sizeof(u_int)
  100. #else
  101. #define RSLOP    0
  102. #endif
  103.  
  104. /*
  105.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  106.  * smallest allocatable block is 8 bytes.  The overhead information
  107.  * precedes the data area returned to the user.
  108.  */
  109.  
  110. #define NBUCKETS    32    /* we can't run out on a 32 bit machine! */
  111. static union overhead * nextf[NBUCKETS];
  112. static union overhead *watchloc = 0;    /* location to be watched */
  113.  
  114. #ifdef MSTATS
  115.  
  116. /*
  117.  * nmalloc[i] is the difference between the number of mallocs and frees
  118.  * for a given block size.
  119.  */
  120.  
  121. static u_int nmalloc[NBUCKETS];
  122.  
  123. #endif
  124.  
  125.  
  126. /*
  127.  * Watch some allocated memory to see if it gets blasted.
  128.  */
  129. allocwatch(cp)
  130.     char *cp;
  131. {
  132.     if (cp == NULL) {
  133.         watchloc = NULL;
  134.         return;
  135.     }
  136.     watchloc = (union overhead *)cp - 1;
  137.     assert(watchloc->ov_magic == MAGIC, 10);
  138. }
  139.  
  140.  
  141. alloccheck()
  142. {
  143.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 11);
  144. }
  145.  
  146.  
  147. /*
  148.  * NAME
  149.  *    morecore - get more memory
  150.  *
  151.  * SYNOPSIS
  152.  *    void
  153.  *    morecore(bucket)
  154.  *    int bucket;
  155.  *
  156.  * DESCRIPTION
  157.  *    Morecore is used to allocate more memory to the indicated bucket.
  158.  *
  159.  * RETURNS
  160.  *    void
  161.  */
  162. static void
  163. morecore(bucket)
  164.     register u_int    bucket;
  165. {
  166.     register union overhead * op;
  167.     register u_int    rnu;    /* 2^rnu bytes will be requested */
  168.     register u_int    nblks;    /* become nblks blocks of the desired size */
  169.     register u_int    siz;
  170.  
  171.     assert(bucket >= QUANTUM_NBITS, 1);
  172.     assert(bucket < NBUCKETS, 2);
  173.     assert(!nextf[bucket], 3);
  174. #ifndef NO_SBRK
  175.     /*
  176.      * Insure memory is allocated on a page boundary.
  177.      * Should make getpageize() call?
  178.      */
  179. #define PAGE_SIZE (1<<10)
  180.     siz = (u_int)sbrk(0);
  181.     if(siz & (PAGE_SIZE-1))
  182.         sbrk(PAGE_SIZE - (siz & (PAGE_SIZE-1)));
  183. #endif
  184.  
  185.     /* take 2k unless the block is bigger than that */
  186.     rnu = (bucket <= 11) ? 11 : bucket;
  187.     assert(rnu >= bucket, 4);
  188.     nblks = 1L << (rnu - bucket); /* how many blocks to get */
  189.     siz = 1L << rnu;
  190.  
  191. #ifndef NO_SBRK
  192.     op = (union overhead *)sbrk(siz);
  193.     /* no more room! */
  194.     if ((int)op == -1)
  195.         return;
  196.     /*
  197.      * Round up to minimum allocation size boundary
  198.      * and deduct from block count to reflect.
  199.      */
  200.     if((int)op & (QUANTUM-1))
  201.     {
  202.         op = (union overhead *)(((int)op + QUANTUM) &~ (QUANTUM-1));
  203.         nblks--;
  204.     }
  205. #else
  206.     op = (union overhead *)malloc(siz);
  207.     /* no more room! */
  208.     if (!op)
  209.         return;
  210. #endif
  211.     /*
  212.      * Add new memory allocated to the
  213.      * free list for this hash bucket.
  214.      */
  215.     nextf[bucket] = op;
  216.     siz = 1L << bucket;
  217.     while (--nblks)
  218.     {
  219.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  220.         op = op->ov_next;
  221.     }
  222. }
  223.  
  224.  
  225. /*
  226.  * NAME
  227.  *    mem_alloc - memory allocator
  228.  *
  229.  * SYNOPSIS
  230.  *    char *
  231.  *    mem_alloc()
  232.  *
  233.  * DESCRIPTION
  234.  *    Mem_alloc is used to allocate memory large enought to fit the requested
  235.  *    size, and on a boundary suitable for placing any value.
  236.  *
  237.  * RETURNS
  238.  *    char *, pointer to base of dynamic memory allocated
  239.  *
  240.  * CAVEAT
  241.  *    Use mem_free() when you are finished with the space.
  242.  */
  243. char *
  244. mem_alloc(nbytes)
  245.     register unsigned long int nbytes;
  246. {
  247.     register union overhead *p;
  248.     register int    bucket;
  249.     register unsigned long int shiftr;
  250.  
  251.     if (nbytes > ((unsigned int) -1))
  252.         return NULL;
  253.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 12);
  254.     /*
  255.      * Convert amount of memory requested into
  256.      * closest block size stored in hash buckets
  257.      * which satisfies request.  Account for
  258.      * space used per block for accounting.
  259.      */
  260.     nbytes = (nbytes + sizeof (union overhead) + RSLOP + (QUANTUM-1)) &~ (QUANTUM-1);
  261.     shiftr = (nbytes - 1) >> QUANTUM_NBITS;
  262.     /* apart from this loop, this is O(1) */
  263.     bucket = QUANTUM_NBITS;
  264.     while(shiftr)
  265.     {
  266.         shiftr >>= 1;
  267.         bucket++;
  268.     }
  269.  
  270.     /*
  271.      * If nothing in hash bucket right now,
  272.      * request more memory from the system.
  273.      */
  274.     if (!nextf[bucket])
  275.         morecore(bucket);
  276.     if (!(p = nextf[bucket]))
  277.         return (char*)0;
  278.     /* remove from linked list */
  279.     nextf[bucket] = p->ov_next;
  280.     p->ov_magic = MAGIC;
  281.     p->ov_index = bucket;
  282. #ifdef MSTATS
  283.     nmalloc[bucket]++;
  284. #endif
  285. #ifdef RCHECK
  286.     /*
  287.      * Record allocated size of block and
  288.      * bound space with magic numbers
  289.      */
  290.     if (nbytes <= (1L<<16))
  291.         p->ov_size = nbytes - 1;
  292.     p->ov_rmagic = RMAGIC;
  293.     *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  294. #endif
  295.     return ((char *)(p + 1));
  296. }
  297.  
  298.  
  299. /*
  300.  * NAME
  301.  *    mem_free - free memory
  302.  *
  303.  * SYNOPSIS
  304.  *    int
  305.  *    mem_free(cp)
  306.  *    char * cp;
  307.  *
  308.  * DESCRIPTION
  309.  *    Mem_free is used to release space allocated by mem_alloc
  310.  *    or mem_realloc.
  311.  *
  312.  * RETURNS
  313.  *    int
  314.  *
  315.  * CAVEAT
  316.  *    do not pass mem_free() an argument that was returned by mem_alloc()
  317.  *    or mem_realloc().
  318.  */
  319. int
  320. mem_free(cp)
  321.     char *    cp;
  322. {
  323.     register u_int    bucket;
  324.     register union overhead *op;
  325.  
  326.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 13);
  327.     if (!cp)
  328.         return;
  329.     op = (union overhead *)cp - 1;
  330.     assert(op->ov_magic == MAGIC, 5);    /* make sure it was in use */
  331.     assert(op->ov_index < NBUCKETS, 6);
  332.     assert(op->ov_index >= QUANTUM_NBITS, 7);
  333. #ifdef RCHECK
  334.     assert(op->ov_index > 16 || op->ov_size == (1L<<op->ov_index)-1, 8);
  335.     assert(op->ov_rmagic == RMAGIC, 9);
  336.     assert(op->ov_index > 16 || *(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC, 10);
  337. #endif
  338. #ifndef DEBUG
  339.     if(op->ov_magic != MAGIC)
  340.         return;        /* sanity */
  341. #endif
  342.     bucket = op->ov_index;
  343.     op->ov_next = nextf[bucket];
  344.     nextf[bucket] = op;
  345. #ifdef MSTATS
  346.     nmalloc[bucket]--;
  347. #endif
  348. }
  349.  
  350.  
  351. /*
  352.  * NAME
  353.  *    findbucket - find a bucket
  354.  *
  355.  * SYNOPSIS
  356.  *    int
  357.  *    findbucket(freep, srchlen)
  358.  *    union overhead * freep;
  359.  *    int srchlen;
  360.  *
  361.  * DESCRIPTION
  362.  *    Findbucket is used to find the bucket a free block is in.
  363.  *    Search ``srchlen'' elements of each free list for a block whose
  364.  *    header starts at ``freep''.  If srchlen is -1 search the whole list.
  365.  *
  366.  * RETURNS
  367.  *    bucket number, or -1 if not found.
  368.  */
  369. static int
  370. findbucket(freep, srchlen)
  371.     union overhead *    freep;
  372.     int    srchlen;
  373. {
  374.     register union overhead *p;
  375.     register int    i, j;
  376.  
  377.     for (i = 0; i < NBUCKETS; i++)
  378.     {
  379.         j = 0;
  380.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next)
  381.         {
  382.             if (p == freep)
  383.                 return i;
  384.             j++;
  385.         }
  386.     }
  387.     return -1;
  388. }
  389.  
  390.  
  391. /*
  392.  * When a program attempts "storage compaction" as mentioned in the
  393.  * old malloc man page, it realloc's an already freed block.  Usually
  394.  * this is the last block it freed; occasionally it might be farther
  395.  * back.  We have to search all the free lists for the block in order
  396.  * to determine its bucket: first we make one pass thru the lists
  397.  * checking only the first block in each; if that fails we search
  398.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  399.  * is extern so the caller can modify it).  If that fails we just copy
  400.  * however many bytes was given to realloc() and hope it's not huge.
  401.  */
  402.  
  403. static int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  404.  
  405. /*
  406.  * NAME
  407.  *    mem_realloc - change size
  408.  *
  409.  * SYNOPSIS
  410.  *    char
  411.  *    mem_realloc(cp, nbytes)
  412.  *    char * cp;
  413.  *    u_int nbytes;
  414.  *
  415.  * DESCRIPTION
  416.  *    Mem_realloc is used to enlarge a chunk of memory
  417.  *    returned by mem_alloc() or mem_realloc().
  418.  *
  419.  * RETURNS
  420.  *    char *, pointer to base of dynamic memory allocated
  421.  *
  422.  * CAVEAT
  423.  *    Use mem_free() when you are finished with the space.
  424.  */
  425. char *
  426. mem_realloc(cp, nbytes)
  427.     char *cp;
  428.     unsigned long    nbytes;
  429. {
  430.     register u_int    old_nbytes;
  431.     register union overhead *op;
  432.     char *    res;
  433.     register u_int    old_bucket;
  434.     short    was_alloced = 0;
  435.  
  436.     if (nbytes > ((unsigned int) -1))
  437.         return NULL;
  438.     assert((watchloc == NULL) || (watchloc->ov_magic == MAGIC), 14);
  439.     if (!cp)
  440.         return mem_alloc(nbytes);
  441.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  442.     if (op->ov_magic == MAGIC)
  443.     {
  444.         was_alloced++;
  445.         old_bucket = op->ov_index;
  446.     }
  447.     else
  448.     {
  449.         /*
  450.          * Already free, doing "compaction".
  451.          *
  452.          * Search for the old block of memory on the
  453.          * free list. First, check the most common
  454.          * case (last element free'd), then (this failing)
  455.          * the last ``realloc_srchlen'' items free'd.
  456.          * If all lookups fail, then assume the size of
  457.          * the memory block being realloc'd is the
  458.          * smallest possible.
  459.          */
  460.         if
  461.         (
  462.             (old_bucket = findbucket(op, 1)) == -1
  463.         &&
  464.             (old_bucket = findbucket(op, realloc_srchlen)) == -1
  465.         )
  466.             old_bucket = QUANTUM_NBITS;
  467.     }
  468.     old_nbytes = (1L << old_bucket) - sizeof(union overhead) - RSLOP;
  469.  
  470.     /*
  471.      * avoid the copy if same size block
  472.      */
  473.     if
  474.     (
  475.         was_alloced
  476.     &&
  477.         nbytes <= old_nbytes
  478.     &&
  479.         nbytes > (old_nbytes >> 1) - sizeof(union overhead) - RSLOP
  480.     )
  481.         return cp;
  482.  
  483.     /*
  484.      * grab another chunk
  485.      */
  486.     if(!(res = mem_alloc(nbytes)))
  487.         return (char*)0;
  488.     assert(cp != res, 11);
  489.     memcpy(res, cp, (nbytes < old_nbytes) ? nbytes : old_nbytes);
  490.     if(was_alloced)
  491.         mem_free(cp);
  492.     return res;
  493. }
  494.  
  495. #else /*!UNIX_MALLOC*/
  496.  
  497. #undef MSTATS
  498.  
  499. #endif /*!UNIX_MALLOC*/
  500.  
  501.  
  502.  
  503. /*
  504.  * Allocate a new item from the specified free list.
  505.  * Returns NULL if no item can be allocated.
  506.  */
  507. ALLOCITEM *
  508. allocitem(fp)
  509.     FREELIST *fp;        /* free list header */
  510. {
  511.     FREEITEM *ip;        /* allocated item */
  512.  
  513.     if (fp->curfree > 0) {
  514.         fp->curfree--;
  515.         ip = fp->freelist;
  516.         fp->freelist = ip->next;
  517.         return (ALLOCITEM *) ip;
  518.     }
  519.     ip = (FREEITEM *) malloc(fp->itemsize);
  520.     if (ip == NULL)
  521.         return NULL;
  522.     return (ALLOCITEM *) ip;
  523. }
  524.  
  525.  
  526. /*
  527.  * Free an item by placing it back on a free list.
  528.  * If too many items are on the list, it is really freed.
  529.  */
  530. void
  531. freeitem(fp, ip)
  532.     FREELIST *fp;        /* freelist header */
  533.     FREEITEM *ip;        /* item to be freed */
  534. {
  535.     if (ip == NULL)
  536.         return;
  537.     if (fp->curfree >= fp->maxfree) {
  538.         free((char *) ip);
  539.         return;
  540.     }
  541.     ip->next = fp->freelist;
  542.     fp->freelist = ip;
  543.     fp->curfree++;
  544. }
  545.  
  546.  
  547. /*
  548.  * NAME
  549.  *    mem_stats - print memory statistics
  550.  *
  551.  * SYNOPSIS
  552.  *    void
  553.  *    mem_stats(s)
  554.  *    char * s;
  555.  *
  556.  * DESCRIPTION
  557.  *    Mem_stats is used to print out statistics about current memory usage.
  558.  *    ``s'' is the title string
  559.  *
  560.  *    Prints two lines of numbers, one showing the length of the free list
  561.  *    for each size category, the second showing the number of mallocs -
  562.  *    frees for each size category.
  563.  *
  564.  * RETURNS
  565.  *    void
  566.  */
  567. /*ARGSUSED*/
  568. void
  569. mem_stats(s)
  570.     char *    s;
  571. {
  572. #ifdef MSTATS
  573.     register int    i, j;
  574.     register union overhead *p;
  575.     int    totfree = 0;
  576.     int    totused = 0;
  577.  
  578.     fprintf(stderr, "Memory allocation statistics %s\n", s);
  579.     fprintf(stderr, "%11s:%12s%12s%12s\n", "Bucket", "In Use", "Free", "Sum");
  580.     for (i = 0; i < NBUCKETS; i++)
  581.     {
  582.         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  583.             ;
  584.         if(!j && !nmalloc[i])
  585.             continue;
  586.         fprintf(stderr, "%11d:%12d%12d%12d\n", (1L<<i), nmalloc[i], j, j+nmalloc[i]);
  587.         totfree += j * (1L << i);
  588.         totused += nmalloc[i] * (1L << i);
  589.     }
  590.     fprintf(stderr, "%11s:%12d%12d%12d\n", "Totals", totused, totfree, totused+totfree);
  591. #else
  592.     fprintf(stderr, 
  593.         "Memory allocation stats were not compiled into calc\n");
  594. #endif
  595. }
  596.  
  597. #ifdef DEBUG
  598. void
  599. assertfailed(n)
  600. {
  601.     printf("Assertion %d failed\n", n);
  602.     exit(1);
  603. }
  604. #endif
  605.  
  606. /* END CODE */
  607.